1. Field of the Invention
The present invention relates to an error correction circuit air correcting an error in recording media by performing error correction of a RS (Reed Solomon) code and error detection of a CRC (cyclic redundancy check code).
2. Description of the Prior Art
The continuous servo method and the sample servo method are admitted in the ISO standards as standard servo methods for optical discs. Of the two servo methods, the continuous servo method uses Reed Solomon codes (RS codes) as error correction codes. The Galois field is GF(2.sup.8) and the primitive polynomial p(X) is determined by: EQU p(X)=X.sup.8 +X.sup.5 +X.sup.3 +X.sup.2 +1 1
The generator polynomial Ge(X) of the Reed Solomon codes is determined by: ##EQU1##
On the other hand, the generator polynomial Gc(X) of the CRC codes is defined as: ##EQU2## where .alpha..sup.i =(.beta..sup.i).sup.88 and .beta. is defined as the clement of the primitive polynomial p(x).
FIG. 10 shows the standard 512 bytes per sector data format on an 90 mm optical disk for the continuous servo method which is admitted as a standard servo method in the ISO standards regarding optical discs. The CRC data C.sub.k (1.ltoreq.k.ltoreq.4), which are generated by coding the CRCs, are found in the following manner.
First, the information polynomial Ic(X) is expressed as: ##EQU3## In FIG. 10, if expressed as An (recording and reproducing are performed in the order of the integer n), every portion of the data is identified as:
User data byte Dn=An (1.ltoreq.n.ltoreq.512); PA1 Pad byte Fm=An (513.ltoreq.n.ltoreq.516); PA1 CRC check byte C.sub.k =An (517.ltoreq.n.ltoreq.520); and PA1 ECC check byte Es,t=An (521.ltoreq.n.ltoreq.600).
The parameters used in Eq. 4 and the parameters m, k, s and t above are defined as: EQU m=n-512 EQU k=n-516 EQU s=[(n-521) mod 5]+1 EQU t=int [(n-521)/5]+1 (5) EQU B.sub.ij =A.sub.n (1.ltoreq.n.ltoreq.520) EQU i=103-int [(n-1)/5] EQU j=(n-1) mod 5
In FIG. 10, indicated at SB are the synchronization bytes and indicated at RS are the re-synchronization bytes.
Hence, the CRC data C.sub.k are calculated by: ##EQU4##
The ECC data Es,t (1.ltoreq.s.ltoreq.5, 1.ltoreq.t.ltoreq.16) which are generated by coding the Reed Solomon codes are found in the following manner.
First, the information polynomial Iej(X) is expressed as: ##EQU5##
Hence, the ECC data Es,t are found by: ##EQU6## FIG. 14 is a block diagram showing the structure of a CRC circuit (CRC generator). Indicated at reference character 7a is an .alpha..sup.40 multiplier, indicated at reference character 7b is an .alpha..sup.117 multiplier, indicated at reference character 7c is an .alpha..sup.228 multiplier, indicated at reference character 7d is an .alpha..sup.97 multiplier, indicated at reference characters 8a, 8b, 8c and 8d are registers, indicated at reference character 9 is an adder, indicated at reference character CLK is a clock, indicated at reference character 11 is a data input terminal, and indicated at reference character 12 is a data output terminal.
Though being obtainable by the calculation method above, the CRC data C.sub.k (1.ltoreq.k.ltoreq.4) may be calculated in the following manner.
First, the information polynomial Icj(X) regarding each code word is expressed as: ##EQU7##
The CRC data C.sub.kj regarding each code word is found by: ##EQU8##
Considering that the CRCs are liner, it is understood that the sum of the respective CRC data C.sub.kj regarding the respective code words is equal to the above-mentioned CRC data C.sub.k. That is, Eq. 11 below holds. ##EQU9##
Now, a method of calculating the CRC data C.sub.kj regarding the respective code words will be described with reference to FIG. 14. The code word number 0 (j=0) will be taken as an example. The information polynomial Ic0(X) for the code word number 0, if expressed in accordance with the data format shown in FIG. 10, is: EQU Ic.sub.0 (X)=D1X.sup.103 +D6X.sup.102 +D11X.sup.101 . . . D511X+F412)
The CRC circuit of FIG. 14 is in fact a divider. Hence, at the end of serial entry of the data from the data input terminal 11 as D1, D6, D11, . . . D511, F4 in accordance with the clock CLK, what is stored in the registers 8a, 8b, 8c and 8d is equal to {Ico(X) X.sup.4 mod Gc(X)}. Therefore, if ##EQU10## the registers 8a, 8b, 8c and 8d store C.sub.10, C.sub.20, C.sub.30 and C.sub.40, respectively.
FIG. 11 is a block diagram showing the structure of a conventional error correction circuit adopting the CRC method. In FIG. 11, a data buffer is indicated at reference character 1. The data buffer 1 stores received data in which an error to be corrected may be included and corrected data which arc obtained after error correction. The received data stored in the data buffer 1 are supplied to a syndrome generator 2 and a CRC generator 5 for every unit of code word number. As shown in FIG. 10, the received data are in the form of data streams in which a plurality of code streams having the CRCs as internal codes and the RS codes as external codes are interleaved. The data streams are classified into a plurality of partial data streams (the vertical data streams of FIG. 10) by the code word numbers. Each partial data stream is coded to include the RS codes.
The syndrome generator 2 calculates a syndrome of the RS codes of a partial data stream of the received data which are stored in the data buffer 1 and outputs the syndrome to an error correction part 4.
In accordance with the syndrome calculated by the syndrome generator 2, the error correction part 4 corrects an error while storing an error location and an error value of the partial data stream in an error location and error value register 3 which is disposed in the error correction part 4.
The CRC generator 5 calculates the CRC in accordance with the partial data stream thus corrected and stored in the data buffer 1 and outputs the CRC to a CRC register 6.
Upon receipt of the CRC of the corrected partial data stream, the CRC register 6 adds data stored therein and the CRC given thereto. The resulting data are then stored in the CRC register 6 to replace the preceding stored data. A total CRC of the whole corrected received data is eventually calculated and outputted by the CRC register 6.
A CRC verification part 35 compares the total CRC which is received from the CRC register 6 with the CRC data which are stored in the data buffer 1 to thereby verify the mis-correction performed by the error correction part 4.
A control circuit 40 supplies a control signal to the syndrome generator 2, the error correction part 4, the CRC generator 5, the CRC register 6 and the CRC verification part 35 to control their operations.
FIGS. 12 and 13 are flow charts showing the error correction performed by the error correction circuit of FIG. 11. In the following, the error correction will be described with reference to FIGS. 12 and 13. The operation hereinafter described is performed under the control of the control circuit 40.
Before starting the sequence, data stored in the CRC register 6 is cleared and received data which may include an error to be corrected is written into the data buffer 1.
First, at a step S1, a code word number counter (not shown in FIG. 11) is set at 0 so that the syndrome generator 2 calculates a syndrome of the partial data stream having a code word number 0 (j=0) of the received data.
If an error is detected, at a step S2, the error correction part 4 derives an error location polynomial and an error value polynomial for the partial data stream having the code word number 0 and calculate the locations and the values of the error from the syndrome which was calculated at the step S1 in accordance with the error location polynomial and the error value polynomial. Next, at a step S3, the error locations and the error values of the partial data stream having the code word number 0 thus found at the step S2 are stored in the error location and error value register 3.
At a step S4, in accordance with the information stored in the error location and error value register 3, the error correction part 4 serially corrects the incorrect partial data stream of the code word number 0 stored in the data buffer 1.
At a step S5, the code word counter increments (a count=j), in response to which the syndrome generator 2 calculates a syndrome of the partial data stream having a code word number j.
Next, at a step S6, the error correction part 4 calculate error locations and error values of the partial data stream having the code word-number j, which is similar to the step S2. At step S7, the error locations and the error values are stored in the error location and error value register 3, similarly to the step S3.
On the other hand, upon completion of the step S5, CRC procedures including the following steps S8 and S9 are performed on a parallel basis with the steps S6 and S7.
At the step S8, the CRC generator 5 calculates the CRC of the corrected partial data stream which has a code word number (j-1) by the afore-mentioned method. At this stage, {Ic(X) X.sup.4 mod Gc(X)} is calculated as the CRC. At the step S9, the CRC register 6 adds the data stored therein (initially 0) and the CRC which was calculated at the step S8. The result is stored in the CRC register 6 as new data.
The sequence proceeds to a step S10 when the steps S7 and S9 are completed. At the step S10, in accordance with the error locations and the error values stored in the error location and error value register 3, the error correction part 4 serially corrects the incorrect partial data stream having the code word number j stored in the data buffer 1.
At a step S11, whether the code word number count j coincides with the last code word number is decided. If the code word number count j does not coincide with the last code word number, the sequence returns to the step S5, the code word number count j is incremented, and the steps S5 to S9 are performed once again.
Conversely, if it is found that the code word number count j coincides with the last code word number at the step S11, the sequence proceeds to a step S12.
At the step S12, the CRC generator 5 calculates the CRC of the corrected partial data stream having the last code word number (5 in the example shown in FIG. 10) in a similar manner to the step S8.
At a step S13, the CRC register 6 adds the data stored therein and the CRC which was calculated at the step S12 and stores the result as new data to be stored therein.
As a result, the data stored in the CRC register 6 coincide with the CRC data C.sub.k yielded by Eq. 11. At a step S14, the CRC verification part 35 compares the CRC data C.sub.k which were obtained at the step S13 with the CRC data C.sub.k which were generated by the error correction and stored in the data buffer 1 to thereby verify the mis-correction performed using the RS codes.
In the conventional error correction circuit having such a construction above, calculation of a syndrome of the RS codes of the received data having the code word number j (the step S5 of FIG. 12) cannot be performed concurrently with CRC coding of the corrected received data having the code word number (j-1) (the step S8 of FIG. 12). This is because the two steps require that the received data having different code word numbers are read from the one and only data buffer 1.
It then follows that it is error correction based on a syndrome of the received data having the code word number j performed by the error correction part 4 (the steps S6 and S7 of FIGS. 12 and 13) and CRC coding of the received data having the code word number (j-1) performed by the CRC generator 5 (the steps S8 and S9 of FIGS. 12 and 13) that can be performed on a parallel basis.
Hence, no matter how fast the error correction part 4 is capable of performing error correction, the error correction sequence as a whole cannot be finished at an improved speed since CRC coding by the CRC generator 5, which is to be performed simultaneously with the error correction, still remains slow.